package com.xyhuo.leetcode.december;

import java.util.ArrayList;
import java.util.List;

/**
 * 电话号码的字母组合
 * https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
 *
 * @time 2023/12/7
 */
public class LetterCombinations {

//    public static void main(String[] args) {
//        LetterCombinations lc = new LetterCombinations();
//        lc.letterCombinations("23");
//    }

    public List<String> letterCombinations(String digits) {
        if (null == digits || digits.isEmpty()) {
            return ans;
        }
        List<Character>[] list = new List[10];
        for (int i = 2; i < 10; i++) {
            list[i] = new ArrayList<>();
        }
        list[2].add('a');
        list[2].add('b');
        list[2].add('c');

        list[3].add('d');
        list[3].add('e');
        list[3].add('f');

        list[4].add('g');
        list[4].add('h');
        list[4].add('i');

        list[5].add('j');
        list[5].add('k');
        list[5].add('l');

        list[6].add('m');
        list[6].add('n');
        list[6].add('o');

        list[7].add('p');
        list[7].add('q');
        list[7].add('r');
        list[7].add('s');

        list[8].add('t');
        list[8].add('u');
        list[8].add('v');

        list[9].add('w');
        list[9].add('x');
        list[9].add('y');
        list[9].add('z');

        char[] charArray = digits.toCharArray();
        dfs(list, charArray, 0, "");
        return ans;
    }

    List<String> ans = new ArrayList<>();

    private void dfs(List<Character>[] dp, char[] chars, int index, String str) {
        if (index >= chars.length) {
            ans.add(str);
            return;
        }
        int num = chars[index] - '0';
        for (Character item : dp[num]) {
            dfs(dp, chars, index + 1, str + item);
        }
    }
}
